package alogrithm;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/18 18:35
 */
public class KMP {

    public int kmp(String S, String T) {
        int m = S.length();
        int n = T.length();
        int[] next = new int[n];
        getNext(next, S);
        for (int i = 1, j = 0; i < n; ++i) {
            while (j > 0 && S.charAt(j) != T.charAt(i)) {
                j = next[j - 1];
            }
            if (S.charAt(j) == T.charAt(i)) {
                j++;
            }
            if (j == m) {
                return (i - m + 1);
            }
        }

        return -1;
    }

    private void getNext(int[] next, String s) {
        next[0] = 0;
        for (int i = 1, j = 0; i < s.length(); ++i) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                ++j;
            }
            next[i] = j;
        }
    }
}
